package com.hyb.algorithm.data.struct.dp;

/**
 * @author: ybhu
 * @create: 2021/08/26 07:53
 */
public class StringMatch {

    public static void main(String[] args) {
        StringMatch stringMatch = new StringMatch();

        boolean t = stringMatch.isMatch("ab", ".*");

        System.out.println(t);
    }


    public boolean isMatch(String text, String pattern) {

        //dp[i][j]表示 text 从 i 开始到最后，pattern 从 j 开始到最后，此时 text 和 pattern 是否匹配。

        return true;
    }


    public boolean isMatch3(String text, String pattern) {

        //如果 pattern 为空  那么判断 text 是不是也是空字符串
        if (pattern.isEmpty())
            return text.isEmpty();

        boolean firstMatch = !text.isEmpty() && (text.charAt(0) == pattern.charAt(0) || (pattern.charAt(0) == '.'));


        //处理 * 匹配
        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {


            //两种情况  第一种情况  首字母匹配了  text=aa  pattern=a*
            boolean one = firstMatch && isMatch(text.substring(1), pattern);

            //p[i] 也有可能匹配 0 个字符，比如 s = "aa", p = "a*aa"，由于后面的字符可以匹配 s，所以 p[0] 只能匹配 0 次。
            //第二种情况   text=aa  pattern=a*aa  此时 a* 可能是0次 pattern 截取2个字符转换为aa
            boolean two = isMatch(text, pattern.substring(2));


            return two || one;
        } else {

            //判断是否第一个字符匹配  且  截取一个字符 后 是否还是匹配
            return firstMatch && isMatch(text.substring(1), pattern.substring(1));
        }

    }


    public boolean isMatch2(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();

        boolean first_match = (!text.isEmpty() &&
                (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
        //只有长度大于 2 的时候，才考虑 *
        if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
            //两种情况
            //pattern 直接跳过两个字符。表示 * 前边的字符出现 0 次
            //pattern 不变，例如 text = aa ，pattern = a*，第一个 a 匹配，然后 text 的第二个 a 接着和 pattern 的第一个 a 进行匹配。表示 * 用前一个字符替代。
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }

}
